/*
 * @lc app=leetcode.cn id=34 lang=typescript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
function searchRange(nums: number[], target: number): number[] {
  const binarySearch = (nums: number[], target: number): number => {
    let head = 0;
    let tail = nums.length - 1;

    while (head <= tail) {
      let mid = ((tail - head) >> 1) + head;
      if (nums[mid] < target) head = mid + 1;
      else tail = mid - 1;
    }

    return head;
  };

  const result = new Array(2);
  // 先找第一个大于等于targt的元素
  let i = binarySearch(nums, target);
  // 验证元素的合法性
  if (i === nums.length || nums[i] !== target) return [-1, -1];
  // 找第一个大于等于target+1的元素
  // 如果只有一个元素的话，需要将边界合法
  let j = Math.max(0, binarySearch(nums, target + 1) - 1);

  return [i, j];
}
// @lc code=end
